Digital adaptive transversal finite impulse response (AFIR) filters have recently become an important tool in signal processing. The theory of AFIR filters is described in "Identification Algorithm for Adaptive Filters", Comsat Technical Review, O. A. Horna, Volume 8, No. 2, Fall, 1978, pp 331-351.
FIG. 1 is an illustration of one such filter. An input signal X is applied on the one hand to tap delay line 10 having a number of equi-distant taps, each of the taps equipped with an adjustable coefficient h.sub.j. The input signal X is also applied to the echo feedback path through an identified system. The identified system includes a "flat delay" t.sub.fd, and an impulse response H(t). The signal X, as well as the system output d, are applied to the delay line 10 and the error detector 30, respectively, under the selective control of sampler 35.
The output h.sub.j of each of the adjustable amplitude devices, is applied to linear combiner 15 which sums the products x.sub.ij h.sub.j, where x.sub.ij are samples of the input signal X present at the ith sampling interval at the j-th tap, to produce the output x.sub.i.sup.T h. The identified system output d is subtracted from the system output from combiner 15 in error detector 30 to produce error signal e.sub.m, which in turn is applied to error storage device 25. The errors e.sub.m are delivered from the error storage device 25 to correction processor 20. Correction processor 20 computes corrections .DELTA.h.sub.j which change the coefficients h.sub.j so as to drive the error value e.sub.m to zero. Thus, the output of the AFIR filter is as close a replica of the output of the identified system H(t)+t.sub.fd as possible.
The prior art device of FIG. 1 will work properly as long as the number of coefficients is relatively small (on the order of 10 or less) or if the samples of the input reference signal X are uncorrelated over time. Wideband white noise and Poisson waves are examples of a signal having this property. However, voice, music and video signals have autocorrelation coefficients of adjacent samples .delta..sub.xx &gt;0.8 when sampled at the Nyquist rate. Thus, for "long filters" where the number of taps is greater than 30, decorrelation of the input signals entering the correction processor must be performed in order to permit the AFIR filter to converge to a stable state, i.e., a stable coefficient vector h.
A very effective prior art decorrelation technique is illustrated in FIG. 2. Both the error vector e.sub.m stored in the error storage register 25 and the signal vector x.sub.i stored in the AFIR filter 5 are multiplied or "dithered" by generators 45 and 55 which produce random sequences of ones and zeros F.sub.e and .phi..sub.x, respectively, before entering the correction processor.
Although the number of taps in the filter may be increased and still provide the generation of a stable vector h for correlated signals, this decorrelation method substantially reduces the speed of the adaptation process for producing the coefficients h.sub.j. Rather than multiplying the error and signal vectors by purely random sequences, a better solution exists in providing a pseudorandom dither which selects for processing only those samples x.sub.ij and e.sub.i greater than a predetermined value. Such a system is described in U.S. Pat. No. 4,064,379 to O. A. Horna.
Direct analog implementation of the AFIR filters of FIG. 1 or 2 is difficult. A wideband delay line with several milliseconds delay is difficult to implement electronically, and a direct electronic permanent or semi-permanent analog memory having the requisite precision does not yet exist. Therefore, typical AFIR filters, such as the one described in U.S. Pat. No. 4,064,379 typically use digital techniques.
FIG. 3 is an illustration of a digital embodiment of a prior art AFIR filter. Input signal X is applied to the inputs of A to D converter 55 and the identified system under the selective control of sampler 35. The output of A to D converter 55 is selectively applied to X register 60 and multiplier 70 via switch S under the control of sampler 35 and delay device 35'. The delay device 35' provides an amount of delay equal to the analog-to-digital conversion time of converter 55. At all other times, switch S is in the "a" position to allow for the recirculation of the values x.sub.j in X register 60.
The output of X register 60 is applied to detector 80, pseudorandom sequence generator 85, and correction processor 20'. Detector 80 detects the square root of the sum of the squares of the contents of the X register. The output of detector 80 is applied on the one hand to pseudorandom generator means 85, and on the other hand to pseudorandom generator means 90. Pseudorandom generator means 90 receives a second input from the output of subtractor 30, and provides the pseudorandom sequence F.sub.i to correction processor 20'. The output of pseudorandom processor 85 provides the pseudorandom sequence .phi..sub.j to correction processor 20'. Correction processor 20' receives a further input directly from the output of subtractor 30. Finally, correction processor 20' receives its final input from the h.sub.n stage of H register 65. The present corrected coefficient value h.sub.n+1 as calculated by correction processor 20' is delivered to the h.sub.n+1 stage of H register 65, the value of which is applied to multiplier 70 on the one hand and recirculated to the first stage of H register 65, namely h.sub.o, to provide the recirculation of the h vector.
Each of the stages of shift registers 60 and 65 actually comprises a multibit storage element, 8 bits for example, such that an 8-bit value in each of the storage elements is sequentially clocked to an adjacent storage element. Random access memories could be used as an alternative to shift registers 60 and 65 if so desired.
The output of the multiplier 70 is applied to accumulator 75 which functions accumulate the most recent n+1 products. The output of accumulator 75 is applied to D to A converter 95, which in turn provides the system output and an input to the negative terminal of subtractor 30.
The details of correction processor 20', and pseudorandom generators 85 and 90 are given in the above cited article in Comsat Technical Review, as well as in "Echo Canceller with Adaptive Transversal Filter Utilizing Pseudologarithmic Coding " by O. A. Horna, Comsat Technical Review, Volume 7, No. 2, Fall 1977, pp. 393-428, and from the above cited U.S. Pat. No. 4,064,379.
The X register 60, having n+1 stages, and the H register 65, having n+2 stages are clocked at a rate (n+1)F.sub.s, where F.sub.s is the sampling rate of sampler 35, to thereby effect a convolution shift of the X and h vectors. However, the same convolution shift can be achieved using X and H registers having an equal number of stages by adding an additional clock pulse to the X register each sampling period. For each sampling period, the contents of registers 60 and 65 will have shifted n+1 stages. During the next clock pulse (n+2), the switch S is put in the "b" position under the control of sampler 35 and delay device 35', such that the next sample is placed in the X register. Since this occurs after n+2 shifts of the n+1 stage shift register, each sample effectively propagates through the registers one stage per each sampling period to thereby effectively provide the delay element 10, FIG. 1, while at the same time being circulated, multiplied and accumulated within each sampling period 1/F.sub.s to effect the summation performed by element 15, FIG. 1. Thus, the sample Y(i) of the estimated response of the system H(t)+t.sub.fd is produced at the end of each cycle, where ##EQU1##
The contents of the last stage x.sub.n of shift register 60 are destroyed once per sampling period when switch S is in position "b" to accept the new sample.
Since the processing in the digital AFIR filter is serial, i.e., during one sampling period the partial products x.sub.ij h.sub.j are computed sequentially and sequentially added into the accumulator, the sampling rate and the number of coefficients are limited by the speed of the shift registers and the speed of the multiplier and accumulator. With present digital circuits and with a sampling rate of 10 kHz, the maximum number of coefficients must typically be less than 300 to thereby provide a whole impulse response for the identified system of no longer than 30 milliseconds. While these values may be sufficient to handle the responses and delays in long distance telephone networks, they are insufficient to handle broadcast quality speech or systems having a long t.sub.fd, such as acoustic feedback between microphone and loudspeaker in a public address system, or acoustic problems in teleconferencing, since t.sub.fd, as well at the system response, must be stored by the h coefficients in register 65.